package leetcode.code1765;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.IDebug;

//执行用时：53 ms, 在所有 Java 提交中击败了49.65%的用户
//
//内存消耗：146.1 MB, 在所有 Java 提交中击败了30.07%的用户
//
//通过测试用例：59 / 59
public class Solution implements IDebug {

	int m, n;
	int[][] ans;
	boolean[][] been;
	int[][] isWater;

	public int[][] highestPeak(int[][] isWater) {
		m = isWater.length;
		n = isWater[0].length;
		ans = new int[m][n];
		been = new boolean[m][n];
		this.isWater = isWater;
		Queue<int[]> queue = new LinkedList<>();
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (isWater[i][j] == 1) {
					this.updateAns(i, j, 0, queue);
				}
			}
		}
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int x = cur[0], y = cur[1];
			int h = ans[x][y];
			this.updateAround(x, y, h + 1, queue);
		}
		return ans;
	}

	private void updateAround(int x, int y, int h, Queue<int[]> queue) {
		this.update(x + 1, y, h, queue);
		this.update(x - 1, y, h, queue);
		this.update(x, y + 1, h, queue);
		this.update(x, y - 1, h, queue);
	}

	private void update(int x, int y, int h, Queue<int[]> queue) {
		if (x < 0 || x >= m || y < 0 || y >= n || been[x][y]) {
			return;
		}
		this.updateAns(x, y, h, queue);
	}

	private void updateAns(int x, int y, int h, Queue<int[]> queue) {
		this.ans[x][y] = h;
		this.been[x][y] = true;
		queue.add(new int[] { x, y });
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
